package org.example.ch14;

import com.sun.javafx.scene.traversal.SubSceneTraversalEngine;

import java.util.*;

/**
 * N皇后问题
 * https://leetcode-cn.com/problems/n-queens/
 *
 */
public class SolveNQueens {

    public static void main(String[] args) {
        SolveNQueens nQueens = new SolveNQueens();
        List<List<String>> list= nQueens.solveNQueens(4);
        System.out.println("一共有"+list.size()+"种解法");
        for (List<String> listArr : list){
            for (String str:listArr){
                System.out.println(str);
            }
            System.out.println("========================");
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens,-1);

        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions,queens,n,0,columns,diagonals1,diagonals2);

        return solutions;
    }

    private void backtrack( List<List<String>> solutions,
                           int[] queens,
                           int n, int row,
                           Set<Integer> columns,
                           Set<Integer> diagonals1,
                           Set<Integer> diagonals2) {
        if(row == n){
            List<String> board = generateBoard(queens,n);
            solutions.add(board);
            System.out.println("diagonals1:"+diagonals1.toString());
            System.out.println("diagonals2:"+diagonals2.toString());
        }else{
            for (int i = 0; i < n; i++) {
               if(columns.contains(i)){
                   continue;
               }
               int d1 = row - i;
               if(diagonals1.contains(d1)){
                   continue;
               }
               int d2 = row + i;
               if(diagonals2.contains(d2)){
                   continue;
               }
               queens[row] = i;
               columns.add(i);
               diagonals1.add(d1);
               diagonals2.add(d2);
               backtrack(solutions,queens,n,row+1,columns,diagonals1,diagonals2);
               //回溯算法
               queens[row] = -1;
               columns.remove(i);
               diagonals1.remove(d1);
               diagonals2.remove(d2);

            }
        }
    }

    public List<String> generateBoard(int[] queens,int n){
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row,'.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

